package argo.hot100.tree;

import java.util.Stack;

public class InvertTree {

    public TreeNode invertTree(TreeNode root) {
        TreeNode p = root, p1 = null, pre = null;

        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || p != null) {
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
            p = stack.pop();
            if (p.right == null || pre == p.right) {
                p1 = p.right;
                p.right = p.left;
                p.left = p1;

                pre = p;
                p = null;
            } else {
                stack.push(p);
                p = p.right;
            }
        }

        return root;
    }


    public TreeNode invertTreePre(TreeNode root) {
        TreeNode p = root, p1 = null, pre = null;

        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || p != null) {
            while (p != null) {
                p1 = p.right;
                p.right = p.left;
                p.left = p1;

                stack.push(p);
                p = p.left;
            }
            p = stack.pop();
            p = p.right;

        }

        return root;
    }

    public TreeNode invertTreeRecu(TreeNode root) {
        TreeNode p = root;

        invertTreeRecus(p);
        return root;
    }

    public void invertTreeRecus(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode p = null;
        invertTreeRecus(root.left);
        invertTreeRecus(root.right);
        p = root.left;
        root.left = root.right;
        root.right = p;


    }


}
